home *** CD-ROM | disk | FTP | other *** search
/ AP Professional Graphics CD-ROM Library / AP Professional Graphics CD-ROM Library.iso / pc / unix / appendix / gemsi / dbleline.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-02-15  |  4.7 KB  |  197 lines
  1. /*
  2. Symmetric Double Step Line Algorithm
  3. by Brian Wyvill
  4. from "Graphics Gems", Academic Press, 1990
  5.  
  6. user provides "setpixel()" function for output.
  7. */
  8.  
  9. #define swap(a,b)           {a^=b; b^=a; a^=b;}
  10. #define absolute(i,j,k)     ( (i-j)*(k = ( (i-j)<0 ? -1 : 1)))
  11. int
  12. symwuline(a1, b1, a2, b2) int a1, b1, a2, b2;
  13. {
  14.     int           dx, dy, incr1, incr2, D, x, y, xend, c, pixels_left;
  15.     int           x1, y1;
  16.     int           sign_x, sign_y, step, reverse, i;
  17.  
  18.     dx = absolute(a2, a1, sign_x);
  19.     dy = absolute(b2, b1, sign_y);
  20.     /* decide increment sign by the slope sign */
  21.     if (sign_x == sign_y)
  22.         step = 1;
  23.     else
  24.         step = -1;
  25.  
  26.     if (dy > dx) {        /* chooses axis of greatest movement (make
  27.                           * dx) */
  28.         swap(a1, b1);
  29.         swap(a2, b2);
  30.         swap(dx, dy);
  31.         reverse = 1;
  32.     } else
  33.         reverse = 0;
  34.     /* note error check for dx==0 should be included here */
  35.     if (a1 > a2) {        /* start from the smaller coordinate */
  36.         x = a2;
  37.         y = b2;
  38.         x1 = a1;
  39.         y1 = b1;
  40.     } else {
  41.         x = a1;
  42.         y = b1;
  43.         x1 = a2;
  44.         y1 = b2;
  45.     }
  46.  
  47.  
  48.     /* Note dx=n implies 0 - n or (dx+1) pixels to be set */
  49.     /* Go round loop dx/4 times then plot last 0,1,2 or 3 pixels */
  50.     /* In fact (dx-1)/4 as 2 pixels are already plotted */
  51.     xend = (dx - 1) / 4;
  52.     pixels_left = (dx - 1) % 4;    /* number of pixels left over at the
  53.                                   * end */
  54.     plot(x, y, reverse);
  55.     if ( pixels_left < 0 ) return ;    /* plot only one pixel for zero
  56.                             * length vectors */
  57.     plot(x1, y1, reverse);    /* plot first two points */
  58.     incr2 = 4 * dy - 2 * dx;
  59.     if (incr2 < 0) {    /* slope less than 1/2 */
  60.         c = 2 * dy;
  61.         incr1 = 2 * c;
  62.         D = incr1 - dx;
  63.  
  64.         for (i = 0; i < xend; i++) {    /* plotting loop */
  65.             ++x;
  66.             --x1;
  67.             if (D < 0) {
  68.                               /* pattern 1 forwards */
  69.                 plot(x, y, reverse);
  70.                 plot(++x, y, reverse);
  71.                                 /* pattern 1 backwards */
  72.                 plot(x1, y1, reverse);
  73.                 plot(--x1, y1, reverse);
  74.                 D += incr1;
  75.             } else {
  76.                 if (D < c) {
  77.                     /* pattern 2 forwards */
  78.                     plot(x, y, reverse);
  79.                     plot(++x, y += step, reverse);
  80.                     /* pattern 2 backwards */
  81.                     plot(x1, y1, reverse);
  82.                     plot(--x1, y1 -= step, reverse);    
  83.                 } else {
  84.                         /* pattern 3 forwards */
  85.                     plot(x, y += step, reverse);
  86.                     plot(++x, y, reverse);
  87.                     /* pattern 3 backwards */
  88.                     plot(x1, y1 -= step, reverse);
  89.                     plot(--x1, y1, reverse);
  90.                 }
  91.                 D += incr2;
  92.             }
  93.         }        /* end for */
  94.  
  95.         /* plot last pattern */
  96.         if (pixels_left) {
  97.             if (D < 0) {
  98.                 plot(++x, y, reverse);    /* pattern 1 */
  99.                 if (pixels_left > 1)
  100.                     plot(++x, y, reverse);
  101.                 if (pixels_left > 2)
  102.                     plot(--x1, y1, reverse);
  103.             } else {
  104.                 if (D < c) {
  105.                     plot(++x, y, reverse);    /* pattern 2  */
  106.                     if (pixels_left > 1)
  107.                         plot(++x, y += step, reverse);
  108.                     if (pixels_left > 2)
  109.                         plot(--x1, y1, reverse);
  110.                 } else {
  111.                   /* pattern 3 */
  112.                     plot(++x, y += step, reverse);
  113.                     if (pixels_left > 1)
  114.                         plot(++x, y, reverse);
  115.                     if (pixels_left > 2)
  116.                         plot(--x1, y1 -= step, reverse);
  117.                 }
  118.             }
  119.         }        /* end if pixels_left */
  120.     }
  121.     /* end slope < 1/2 */
  122.     else {            /* slope greater than 1/2 */
  123.         c = 2 * (dy - dx);
  124.         incr1 = 2 * c;
  125.         D = incr1 + dx;
  126.         for (i = 0; i < xend; i++) {
  127.             ++x;
  128.             --x1;
  129.             if (D > 0) {
  130.               /* pattern 4 forwards */
  131.                 plot(x, y += step, reverse);
  132.                 plot(++x, y += step, reverse);
  133.               /* pattern 4 backwards */
  134.                 plot(x1, y1 -= step, reverse);
  135.                 plot(--x1, y1 -= step, reverse);
  136.                 D += incr1;
  137.             } else {
  138.                 if (D < c) {
  139.                   /* pattern 2 forwards */
  140.                     plot(x, y, reverse);
  141.                     plot(++x, y += step, reverse);
  142.  
  143.                    /* pattern 2 backwards */
  144.                     plot(x1, y1, reverse);
  145.                     plot(--x1, y1 -= step, reverse);
  146.                 } else {
  147.                   /* pattern 3 forwards */
  148.                     plot(x, y += step, reverse);
  149.                     plot(++x, y, reverse);
  150.                   /* pattern 3 backwards */
  151.                     plot(x1, y1 -= step, reverse);
  152.                     plot(--x1, y1, reverse);
  153.                 }
  154.                 D += incr2;
  155.             }
  156.         }        /* end for */
  157.         /* plot last pattern */
  158.         if (pixels_left) {
  159.             if (D > 0) {
  160.                 plot(++x, y += step, reverse);    /* pattern 4 */
  161.                 if (pixels_left > 1)
  162.                     plot(++x, y += step, reverse);
  163.                 if (pixels_left > 2)
  164.                     plot(--x1, y1 -= step, reverse);
  165.             } else {
  166.                 if (D < c) {
  167.                     plot(++x, y, reverse);    /* pattern 2  */
  168.                     if (pixels_left > 1)
  169.                         plot(++x, y += step, reverse);
  170.                     if (pixels_left > 2)
  171.                         plot(--x1, y1, reverse);
  172.                 } else {
  173.                   /* pattern 3 */
  174.                     plot(++x, y += step, reverse);
  175.                     if (pixels_left > 1)
  176.                         plot(++x, y, reverse);
  177.                     if (pixels_left > 2) {
  178.                         if (D > c) /* step 3 */
  179.                            plot(--x1, y1 -= step, reverse);
  180.                         else /* step 2 */
  181.                             plot(--x1, y1, reverse);
  182.                                  }
  183.                 }
  184.             }
  185.         }
  186.     }
  187. }
  188. /* non-zero flag indicates the pixels needing swap back. */
  189. plot(x, y, flag) int x, y, flag;
  190. {
  191.     if (flag)
  192.         setpixel(y, x);
  193.     else
  194.         setpixel(x, y);
  195. }
  196.  
  197.